package com.leetcode.根据数据结构分类.数组;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author: ZhouBert
 * @date: 2021/2/1
 * @description: 888. 公平的糖果棒交换
 * https://leetcode-cn.com/problems/fair-candy-swap/
 */
public class A_888_公平的糖果棒交换 {

	public static void main(String[] args) {
		int[] A = new int[]{1, 1};
//		A = new int[]{1, 2};
//		A = new int[]{2};
//		A = new int[]{1, 2, 5};
		int[] B = new int[]{2, 2};
//		B = new int[]{2, 3};
//		B = new int[]{1, 3};
//		B = new int[]{2, 4};
		A_888_公平的糖果棒交换 action = new A_888_公平的糖果棒交换();
		int[] res = action.fairCandySwap(A, B);
		System.out.println(Arrays.toString(res));
	}

	/**
	 * 这道题不太好理解，我最终的理解是：
	 * 1.只会交换一次；
	 * 2.交换的索引的值，分别是 ans[0] ans[1]
	 * --
	 * 那么我的解法是：
	 * 1.遍历全部，计算总值，各自总值，及平均数，并借助 hashMap 保存 value-index
	 * 2.计算插值，遍历较少的数组，寻找 hashMap 的 value O(1) 得出
	 * --
	 * 反思：
	 * 这是个数学问题，但是我考虑的太复杂了：
	 * int delta = (sumA - sumB) / 2;
	 * delta = xa - xb;
	 * 用 delta 直接去判断 哈希表即可，而不用再去讨论从 A 还是 B 入手
	 * @param A
	 * @param B
	 * @return
	 */
	public int[] fairCandySwap(int[] A, int[] B) {
		int[] res = new int[2];
		int aLen = A.length;
		int bLen = B.length;
		//将少的部分作为遍历的对象
		boolean aLonger = aLen > bLen ? true : false;
		int aSum = 0, bSum = 0, interval = 0;
		// value - index 记录长的映射
		HashMap<Integer, Integer> aMap = new HashMap<>();
		HashMap<Integer, Integer> bMap = new HashMap<>();
		for (int i = 0; i < aLen; i++) {
			aSum += A[i];
			aMap.put(A[i], i);
		}
		for (int i = 0; i < bLen; i++) {
			bSum += B[i];
			bMap.put(B[i], i);
		}

		//计算差值
		interval = Math.abs(aSum - ((aSum + bSum) >> 1));
		int tempValue = 0;
		boolean aBigger = aSum > bSum ? true : false;
		if (aLonger && aBigger) {
			//如果 A 比较长 && A 比较大
			//-> 遍历 B
			for (int i = 0; i < bLen; i++) {
				tempValue = B[i] + interval;
				if (aMap.containsKey(tempValue)) {
					res[0] = tempValue;
					res[1] = B[i];
					break;
				}
			}
		} else if (aLonger && !aBigger) {
			for (int i = 0; i < bLen; i++) {
				tempValue = B[i] - interval;
				if (aMap.containsKey(tempValue)) {
					res[0] = tempValue;
					res[1] = B[i];
					break;
				}
			}
		} else if (!aLonger && aBigger) {
			for (int i = 0; i < aLen; i++) {
				tempValue = A[i] - interval;
				if (bMap.containsKey(tempValue)) {
					res[0] = A[i];
					res[1] = tempValue;
					break;
				}
			}
		} else {
			for (int i = 0; i < aLen; i++) {
				tempValue = A[i] + interval;
				if (bMap.containsKey(tempValue)) {
					res[0] = A[i];
					res[1] = tempValue;
					break;
				}
			}
		}

		return res;
	}
}
